package 字符串;

/**
 * 买卖股票的最佳时机
 * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
    你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
    返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

 思路：方式一：采用暴力的思路
    对于每一组的i和 j （j>i）,只需要找出max（prices[j] - prices[i]） 即可。
    但是这种方式会超时。
    所以我们需要进行优化
    方式2：代入上帝视角，既然算最大利润，我们只需要一次遍历，计算出哪天购买是最小花费，
    然后对比出前i天的最高股价，卖出即可。
    买卖股票不要想太多，因为只卖出一次，所以找到最低购买点，在最高股价卖出即可。
 */
public class L_121 {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE;
        int profit = 0;
        for(int price : prices){
            // 前i天的最低股价点
            cost = Math.min(cost,price);
            // 对比出股价最高的那天卖出即可
            profit = Math.max(profit,price - cost);
        }
        return profit;
    }
}
